home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Cream of the Crop 1
/
Cream of the Crop 1.iso
/
PROGRAM
/
NTUMIN10.ARJ
/
READF.C
< prev
next >
Wrap
C/C++ Source or Header
|
1992-03-12
|
13KB
|
387 lines
/****************************************************************************
*
* Program name : READF.C
*
* Written By : Eng-Huat Ong and Kian-Mong Low.
*
* This program reads the cubes from the input file, converts them to
* minterms and then packs them in bits in the main memory.
*
* Returns solution array if cube of all X's found
* else an array of minterms
*
* --------------------------------------------------------------------------
* Copyright (c) 1992. All Rights Reserved. Nanyang Technological
* University.
*
* You are free to use, copy and distribute this software and its
* documentation providing that:
*
* NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
*
* IT IS NOT MODIFIED IN ANY WAY.
*
* THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
*
* This program is provided "AS IS" without any warranty, expressed or
* implied, including but not limited to fitness for any particular
* purpose.
*
* If you find NTUMIN fast, easy, and useful, a note or comment would be
* appreciated. Please send to:
*
* Boon-Tiong Tan or Othman Bin Ahmad
* School of EEE
* Nanyang Technological University
* Nanyang Avenue
* Singapore 2263
* Republic of Singapore
*
***************************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define mask8 255
unsigned char *readf(fp, a, ondc)
FILE *fp;
unsigned char ondc, *a;
{
unsigned char nspm, l, mterm, x, x_count, c, bptr=0, bit_num;
unsigned char *temp, *hold, *nn, *cnn, *px, *cube, *p, *b;
unsigned long m, k, mlast;
unsigned short n, cu, i;
unsigned long mem, terms, topow(), m_cnt, test, ccube;
char e, j, exist();
/***
*** READ NO. OF VARIABLES AND NO. OF CUBES FROM INPUT FILE
***/
if (ondc == 0) /* ON array */
{
nn = (unsigned char *) malloc(4); /* space for no. of var */
if (nn==0)
{
printf("Out of Memory -- READF, *nn\n");
printf("Program terminated - 1\n");
exit(0);
}
n = 0;
while (n == 0) /* take care of leading blank lines */
{
fgets(nn, 4, fp); /* read no. of variable */
n = atoi(nn); /* ascii to integer */
}
if (n > 255) /* exceed max limit */
{
printf("No. of variables exceeded maximum limit of 255 in input file.\n");
printf("Program terminated.\n");
exit(0);
}
mlast = 0; /* reset no. of minterms */
nspm = (n+7)/8; /* no. bytes/minterm */
mem = 4 + nspm; /* amount to allocate */
a = (unsigned char *) malloc(mem); /* space for a -array */
if (a==0)
{
printf("Out of memory -- READF, *a\n");
printf("Progam terminated - 2\n");
exit(0);
}
*a = n; /* no. of variable */
*(a+3) = nspm; /* no. of storage per minterm */
}
else /* DC array, ondc = 1 */
{
n = *a; /* no. of variables */
nspm = *(a+3); /* no. of bytes/minterm */
mlast = *(a+1) | *(a+2)<<8; /* no. of minterms from ON array */
mem = 4 + nspm*(1+mlast); /* allocate in advance for next term */
}
cnn = (unsigned char *) malloc(8); /* space for no. of cubes */
if (cnn==0)
{
printf("Out of Memory -- READF, *cnn\n");
printf("Program terminated - 3\n");
exit(0);
}
fgets(cnn, 8, fp); /* read no. of cubes */
cu = atoi(cnn); /* ascii to integer */
/***
*** BREAK THE CUBES INTO MINTERMS IF ANY
***/
if (cu != 0) /* cube count not zero */
{
cube = (unsigned char *)malloc(n+12); /* space for cube */
if (cube==0)
{
printf("Out of Memory -- READF, *cube\n");
printf("Program terminated - 4\n");
exit(0);
}
px = (unsigned char *)malloc(n+1); /* space for position of X */
if (px==0)
{
printf("Out of Memory -- READF, *px\n");
printf("Program terminated - 5\n");
exit(0);
}
p = (unsigned char *)malloc(n+1); /* space for p-array */
if (p==0)
{
printf("Out of Memory -- READF, *p\n");
printf("Program terminated - 6\n");
exit(0);
}
b = (unsigned char *)malloc(n+1); /* space for b-array */
if (b==0)
{
printf("Out of Memory -- READF, *b\n");
printf("Program terminated - 7\n");
exit(0);
}
temp = (unsigned char *) malloc(nspm+1); /* temporary store */
if (temp==0)
{
printf("Out of Memory -- READF, *temp\n");
printf("Program terminated - 8\n");
exit(0);
}
}
m = mlast; /* no. of minterms */
i = 0;
while (++i<=cu) /* do for all cubes read */
{
x_count = 0; /* no. of X's in a cube */
fgets(cube, n+12, fp); /* get cube from infile */
*(cube+n) = '\0'; /* terminate with NULL string */
x = 0;
for (j=n-1; j>=0; j--) /* reverse the order */
{
if (*(cube+j) == 'x' || *(cube+j) == 'X') /* X encountered */
{
*(px+x++) = n-j-1; /* position of X's in cube */
*(p+n-j-1) = 1; /* 1 in p-array indicates a X */
*(b+n-j-1) = 0; /* position reset to zero */
x_count++; /* no. of X's in a cube */
}
else /* a 0 or 1 encountered */
{
*(p+n-j-1) = 0; /* 0 in p-array indicates a 0 or 1 */
*(b+n-j-1) = *(cube+j); /* position assume input value */
}
}
/***
*** CUBE IS A MINTERM, JUST CONVERT IT INTO BINARY FORM, CHECK THAT IT HAS NOT
*** EXISTED IN A-ARRAY BEFORE STORING IT IN A-ARRAY
***/
if (x_count == 0) /* it is a minterm */
{
c=0; /* a counter */
if (n%8 == 0) /* multiple of bytes */
bit_num = 8;
else /* not multiple of bytes */
bit_num = (n%8); /* remainder */
for (j=0; j<nspm; j++) /* if nspm>1 */
{
bptr = 0; /* reset bit pointer */
*(temp+j) = 0; /* reset temporary storage */
while (bptr++<bit_num || (j!=(nspm-1) && bptr<=8)) /* bit storage operation */
{
ccube = *(cube+n-1-c++)-48; /* ascii to integer */
*(temp+j) = ccube<<(bptr-1) | *(temp+j); /* temporary storage */
}
}
e = exist(temp, a, m); /* temp exist in A ? */
if (e == -1) /* don't exist */
{
memcpy((a+4+nspm*m), temp, nspm); /* store in a-array */
m++; /* no. of minterms */
mem = mem+nspm; /* space required */
a = (unsigned char *) realloc(a, mem); /* space for a-array */
if (a==0)
{
printf("Out of Memory -- READF, *a\n");
printf("Program terminated - 9\n");
exit(0);
}
}
}
/***
*** IF CUBE CONSISTS OF X ONLY, RETURN THE SOLUTION OF ALL X OR ALL -
***/
else if (x_count == n) /* cube with all X's */
{
*a = n; /* no. of variables */
*(a+1) = 1; /* no. of product terms */
*(a+2) = 0;
*(a+3) = 0; /* indicate soln obtained */
if (ondc==0 || (ondc==1 && mlast>0)) /* cube with all X's in ON array */
{
for (j=0; j<n; j++)
*(a+4+j) = 'X'; /* solution cube with all X's */
return (a); /* return solution array */
}
else /* cube with all X's in DC array */
{
for (j=0; j<n; j++)
*(a+4+j) = '-'; /* solution cube with all - */
return (a); /* return solution array */
}
}
else
{
/***
*** CUBE WITH SOME X, SO GENERATE THE 1ST MINTERM AND EXPAND TO
*** GENERATE ALL OTHER MINTERMS COVER BY THE CUBE. CHECK THAT THEY
*** ARE NOT ALREADY PRESENT IN A-ARRAY AND STORE THEM IN A-ARRAY
***/
l=0; /* counters */
k=0;
mterm=0; /* temporary storage */
/***
*** GENERATE 1ST MINTERM
***/
for (j=0; j<n; j++) /* do for no. of var */
{
if (*(b+j) == '1') /* a 1 in bit position */
mterm += topow(k); /* convert to binary */
k++;
if (k==8 && ++l<=nspm) /* new byte required */
{
*(temp+l-1)=mterm; /* store the completed byte */
k=0; /* reset counter */
mterm=0; /* reset for new byte */
}
if (k==n-8*l) /* less than 8-bit remains */
*(temp+l) = mterm; /* transfer to temp */
}
/***
*** STORE 1ST MINTERM IN A-ARRAY IF NOT ALREADY EXISTED
***/
e = exist(temp, a, m); /* minterm exist ? */
if (e == -1) /* don't exist */
{
memcpy((a+4+nspm*m), temp, nspm); /* store in a-array */
m++; /* no. of minterms */
mem = mem+nspm; /* space required */
a = (unsigned char *) realloc(a, mem); /* more space */
if (a==0)
{
printf("Out of Memory -- READF, *a\n");
printf("Program terminated - 10\n");
exit(0);
}
}
/***
*** EXPAND USING THE 1ST MINTERM BASE ON THE NO. OF X AND THEIR POSITION
***/
hold = (unsigned char *) malloc(nspm+1); /* temporary storage */
if (hold==0)
{
printf("Out of Memory -- READF, *hold\n");
printf("Program terminated - 11\n");
exit(0);
}
m_cnt = 0; /* counter to simulate binary expansion */
for (j=0; j<x_count; j++) /* expand for the no. of X */
{
terms = topow(j); /* no. of terms required in expansion */
for (k=1; k<=terms; k++) /* for all required terms */
{
m_cnt++; /* simulate binary expansion */
memcpy(hold, temp, nspm); /* transfer 1st minterm */
for (l=0; l<=j; l++) /* no. of times = pos of X */
{
test = m_cnt & (1<<l); /* addition required ? */
if (test != 0)
*(hold + *(px+l)/8) = *(hold + *(px+l)/8) /* add */
+ topow(*(px+l)%8);
}
/***
*** STORE THE GENERATED MINTERM IF NOT ALREADY EXISTED IN A-ARRAY
***/
e = exist(hold, a, m); /* minterm exist in a-array ? */
if (e == -1) /* don't exist */
{
memcpy((a+4+nspm*m), hold, nspm); /* store in a-array */
m++; /* no. of minterms */
mem = mem+nspm; /* space required */
a = (unsigned char *) realloc(a, mem); /* more space */
if (a==0)
{
printf("Out of Memory -- READF, *a\n");
printf("Program terminated - 12\n");
exit(0);
}
}
}
}
free(hold); /* free pointer */
}
}
if (ondc == 0) /* ON-array processed */
free(nn);
free(cnn);
if (cu != 0) /* cube(s) processed */
{
free(cube); /* free pointers used */
free(px);
free(b);
free(p);
free(temp);
}
if (m > 65535) /* max no. of minterms exceeded */
{
printf("Maximum number of minterms exceeded !\n");
printf("Program terminated.\n");
exit(0);
}
*(a+1) = m & mask8; /* no. of minterms in 2 bytes */
*(a+2) = m >> 8;
return(a); /* return array of minterms */
}